package com.c2b.algorithm.leetcode.lcr;

import java.util.HashMap;
import java.util.Map;

/**
 * <a href="https://leetcode.cn/problems/lru-cache/">LRU 缓存(LRU Cache)</a>
 * <p>请你设计并实现一个满足<a href="https://baike.baidu.com/item/LRU">LRU (最近最少使用) 缓存</a>约束的数据结构。</p>
 * <p>实现 LRUCache 类：
 * <ul>
 * <li>LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存</li>
 * <li>int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。</li>
 * <li>void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该 逐出 最久未使用的关键字。</li>
 * </ul>
 * 函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。
 * </p>
 * <p>
 *     <b>示例：</b>
 *     <pre>
 * 输入
 *      ["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
 *      [[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
 * 输出
 *      [null, null, null, 1, null, -1, null, -1, 3, 4]
 * 解释
 *      LRUCache lRUCache = new LRUCache(2);
 *      lRUCache.put(1, 1); // 缓存是 {1=1}
 *      lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
 *      lRUCache.get(1);    // 返回 1
 *      lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
 *      lRUCache.get(2);    // 返回 -1 (未找到)
 *      lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
 *      lRUCache.get(1);    // 返回 -1 (未找到)
 *      lRUCache.get(3);    // 返回 3
 *      lRUCache.get(4);    // 返回 4
 *     </pre>
 * </p>
 * <p>
 *     <b>提示：</b>
 *     <ul>
 *         <li>1 <= capacity <= 3000</li>
 *         <li>0 <= key <= 10000</li>
 *         <li>0 <= value <= 10^5</li>
 *         <li>最多调用 2 * 10^5 次 get 和 put</li>
 *     </ul>
 * </p>
 *
 * @author c2b
 * @since 2024/3/20 13:23
 */
public class LCR031 {

    static class LRUCache {

        private final Map<Integer,Node> cache;
        private final Node dummyHead;
        private final Node dummyTail;
        private final int capacity;

        public LRUCache(int capacity) {
            if (capacity <= 0) {
                throw new RuntimeException("capacity must more than 0.");
            }
            this.capacity = capacity;
            this.cache = new HashMap<>(capacity);
            this.dummyHead = new Node(-1, -1);
            this.dummyTail = new Node(-1, -1);
            dummyHead.next = dummyTail;
            dummyTail.prev = dummyHead;
        }

        public int get(int key) {
            Node node = cache.get(key);
            if (node == null) {
                return -1;
            }
            moveNodeToHead(node);
            return node.val;
        }

        public void put(int key, int value) {
            Node node = cache.get(key);
            // 如果当前节点已存在，直接更新节点值即可
            if (node != null) {
                // 更新节点值
                node.setVal(value);
                moveNodeToHead(node);
            }
            // 2.当前节点不存在，需要向缓存中添加新节点
            else {
                node = new Node(key, value);
                // 判断是否超出容量，如果超出容量，则从链表尾删除一个节点
                if (cache.size() == capacity) {
                    cache.remove(dummyTail.prev.key);
                    removeNodeFromTail();
                }
                // 将当前节点添加到链表头并更新缓存
                addNodeToHead(node);
                cache.put(key, node);
            }
        }

        private void removeNodeFromTail() {
            dummyTail.prev.prev.next = dummyTail;
            dummyTail.prev = dummyTail.prev.prev;
        }

        /**
         * 将当前节点移动到链表头部
         */
        private void moveNodeToHead(Node node) {
            // 如果当前节点恰好在链表的头
            if (node.prev == dummyHead) {
                return;
            }
            // 移除当前节点
            node.prev.next = node.next;
            node.next.prev = node.prev;
            // 将当前节点插入到链表头
            addNodeToHead(node);
        }

        private void addNodeToHead(Node node) {
            node.next = dummyHead.next;
            node.prev = dummyHead;
            dummyHead.next.prev = node;
            dummyHead.next = node;
        }

        static class Node{
            private final int key;
            private int val;
            private Node prev;
            private Node next;

            public Node(int key, int val) {
                this.key = key;
                this.val = val;
            }

            public void setVal(int val) {
                this.val = val;
            }
        }
    }

    public static void main(String[] args) {
        LRUCache lruCache = new LRUCache(2);
        lruCache.put(1, 0);
        lruCache.put(2, 2);
        System.out.println(lruCache.get(1));
        lruCache.put(3, 3);
        System.out.println(lruCache.get(2));
        lruCache.put(4, 4);
        System.out.println(lruCache.get(1));
        System.out.println(lruCache.get(3));
        System.out.println(lruCache.get(4));
    }
}
